iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 16
0
自我挑戰組

學習資料結構30天系列 第 16

[Data Structure][Graph] - Topological Sorting

  • 分享至 

  • xImage
  •  

Activity On Vertex (AOV) Network

有向圖形來表示Activity發生的先後順序限制,頂點代表Activity,以邊表示Activity之間的先後關係。

  • AOV Network必須沒有環路
  • 頂點有先後關係。

https://ithelp.ithome.com.tw/upload/images/20181030/20112438HS76OGeRjW.png

  • 上圖中,a點為其他頂點的predecessor。
  • a點有邊指向b點、c點,所以a點是b點和c點的 immediate predecessor。
  • d點是a點b點c點的successor,也是b點c點的 immediate successor。
  • 有很多個immediate predecessor的頂點,像是d點,就必須等待他的predecessor完成以後才能執行。
  • 沒有predecessor的頂點稱為 source vertex。
  • 沒有successor的頂點稱為sink vertex。

從上圖中,可以得到一個順序是: a->b->c->d->e->f->g->h->i
此順序就稱為Topological Order
得到此順序的過程則為Topological Sorting!

參考

細談資料結構 第六版
ISBN 978-986-312-014-8


上一篇
[Data Structure][Graph] - Floyd Algorithm
下一篇
[Data Structure][Graph] - AOE Network!
系列文
學習資料結構30天30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言